package solutions;

import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * 
 * @author Luke Valenta
 * @uid lvalenta
 * @id# 112113230
 * @date February 18 - March 12 2014
 * CMSC420 Project 1
 * Stack-less Traversals of Binary Search Trees
 * 
 * This class is an implementation of a Threaded Binary Search Tree.
 * Supported operations include insertion, querying for the existence 
 * of an element, in-order traversal, and trivial queries about size,
 * height, and emptiness.
 *
 * @param <T> Objects inserted into the tree must be comparable
 */
public class ThreadedBST<T extends Comparable<T>> {
	
	/* Private class variables */
	private Node root; // The root node of the tree
	private int size; // The number of nodes in the tree

	/**
	 * The constructor for the threadedBST
	 * Initialize to a new empty tree with a null root
	 */
	public ThreadedBST() {
		root = null;
		size = 0;
	}

	/**
	 * Insert an element into the threaded BST. New nodes are always added at
	 * the leaf level of the tree.
	 * @param element The element to be inserted into the tree
	 */
	public void insert(T element) {
		// Create the node
		Node toInsert = new Node(element);
		
		// Find the correct place in the tree to insert the node
		Node curr = root;
		boolean done = false;
		if(root == null) {
			// Insert the new node at the root
			/*toInsert.setLeftChild(null);
			toInsert.setLeftThread(true);
			toInsert.setRightChild(null);
			toInsert.setRightThread(true);*/
			root = toInsert;
			size = 1;
			done = true;
		}
		while(!done) {
			int comp = toInsert.getData().compareTo(curr.getData());
			if(comp < 0) {
				if(curr.isLeftThread()) {
					// Insert the new node here
					toInsert.setLeftChild(curr.getLeftChild());
					toInsert.setRightChild(curr);
					curr.setLeftChild(toInsert);
					curr.setLeftThread(false);
					size++;
					done = true;
				} else {
					// Insert in the left subtree
					curr = curr.getLeftChild();
				}
			} else if (comp > 0) {
				if(curr.isRightThread()) {
					// Insert the new node here
					toInsert.setRightChild(curr.getRightChild());
					toInsert.setLeftChild(curr);
					curr.setRightChild(toInsert);
					curr.setRightThread(false);
					size++;
					done = true;
				} else {
					// Insert in the right subtree
					curr = curr.getRightChild();
				}
			} else {
				// The element already exists in the tree
				done = true;
			}
		} // end while loop
	}
	
	/**
	 * An iterator that traverses the tree's elements in order
	 * @return An iterator that traverses the tree's elements in order
	 */
	public Iterator<T> inorderTraversal() {
		return new Iterator<T>() {
			Node next = findFirstNode(root);
			
			private Node findFirstNode(Node n) {
				if(n == null) {
					return null;
				}
				while(!n.isLeftThread()) {
					n = n.getLeftChild();
				}
				return n;
			}
			
			@Override
			public boolean hasNext() {
				if(next != null) {
					return true;
				} else {
					return false;
				}
			}

			@Override
			public T next() {
				if(next == null) {
					throw new NoSuchElementException();
				}
				T toReturn = next.data;
				
				// Replace 'next' with its in-order successor
				boolean isThread = next.isRightThread();
				next = next.getRightChild();
				
				if(!isThread) { // The right link is a pointer to a child
					while(!next.isLeftThread()) {
						next = next.getLeftChild();
					}
				}
				return toReturn;
			}

			@Override
			public void remove() {
				throw new UnsupportedOperationException();
			}
		};
	}
	
	/**
	 * Determines if an element is present in the structure
	 * @param element The element to find
	 * @return Returns true if the element is found in the structure
	 * and false otherwise
	 */
	public boolean find(T element) {
		boolean done = false;
		boolean toReturn = false;
		Node curr = root;
		while(!done) {
			int comp = element.compareTo(curr.getData());
			if(comp < 0) {
				// Search left subtree
				if(!curr.isLeftThread()) {
					// The element might be in the left subtree
					curr = curr.getLeftChild();
				} else {
					// The element is not in the tree
					done = true;
					toReturn = false;
				}
			} else if (comp > 0) {
				// Search the right subtree
				if(!curr.isRightThread()) {
					// The element might be in the right subtree
					curr = curr.getRightChild();
				} else {
					// The element is not in the tree
					done = true;
					toReturn = false;
				}
			} else {
				// We found the element in the tree
				done = true;
				toReturn = true;
			}
		}
		
		return toReturn;
	}
	
	/**
	 * Returns the height of the tree. A stub tree with only the root
	 * has a height of 1.
	 * @return The height of the tree
	 */
	public int height() {
		// TODO: make sure this is allowed. Otherwise, do iteratively.
		return recursiveHeight(root);
	}
	
	private int recursiveHeight(Node node) {
		if(node == null) {
			return 0;
		} else {
			int left = 0, right = 0;
			if(!node.isLeftThread()) {
				left = recursiveHeight(node.getLeftChild());
			}
			if(!node.isRightThread()) {
				right = recursiveHeight(node.getRightChild());
			}
			return 1 + Math.max(left, right);
		}
	}
	
	/*
	private int iterativeHeight(Node node) {
		if(node == null) {
			return 0;
		} else {
			int max = 0;
			while(curr != )
			while
		}
	}
	*/
	
	/**
	 * Find the number of nodes in the tree
	 * @return The number of nodes in the tree
	 */
	public int size() {
		return size;
	}
	
	/**
	 * Determines if the tree contains any elements
	 * @return True if the structure is empty (does not contain 
	 * any elements) and false otherwise
	 */
	public boolean isEmpty() {
		if(size == 0) {
			return true;
		} else {
			return false;
		}
	}
	
	/**
	 * Extra Credit
	 * 
	 * Deletes the first instance of element in the tree. If the
	 * element is not found in the tree, the tree is untouched.
	 * @param element The element to delete
	 *
	public void delete(T element) {
		
		// Find the node to be deleted, while keeping track of the parent
		Node parent = null;
		boolean isLeft = true; // Is the current node the left or the right child of the parent?
		boolean found = false;
		Node curr = root;
		boolean done = false;
		
		// Find the element to remove
		while(!done) {
			int comp = element.compareTo(curr.getData());
			if(comp < 0) {
				// Search left subtree
				if(!curr.isLeftThread()) {
					// The element might be in the left subtree
					parent = curr;
					isLeft = true;
					curr = curr.getLeftChild();
				} else {
					// The element is not in the tree
					found = false;
					done = true;
				}
			} else if (comp > 0) {
				// Search the right subtree
				if(!curr.isRightThread()) {
					// The element might be in the right subtree
					parent = curr;
					isLeft = false;
					curr = curr.getRightChild();
				} else {
					// The element is not in the tree
					found = false;
					done = true;
				}
			} else {
				// We found the element in the tree
				found = true;
				done = true;
			}
		}
		
		if(!found) {
			// The element is not present in the tree, so leave the tree untouched
			return;
		}
		
		// If the node is an internal node (has two children), replace its data with
		// its in-order successor's data, and delete the original copy of that node
		if(!curr.isLeftThread() && !curr.isRightThread()) {
			Node succ = curr.getRightChild();
			Node succParent = curr;
			while(!succ.isLeftThread()) {
				succParent = succ;
				isLeft = true;
				succ = succ.getLeftChild();
			}
			// Copy the data of the successor into the internal node,
			// overwriting the data to be deleted
			curr.setData(succ.getData());
			
			// Set the curr and parent pointers to the node to be deleted
			curr = succ;
			parent = succParent;
		}
		
		// Delete external node (the node has at most one child)
		if(!curr.isLeftThread()) {
			// Replace the removed node with its left child
			if(isLeft) {
				parent.setLeftChild(curr.getLeftChild());
				parent.setLeftThread(false);
			} else {
				parent.setRightChild(curr.getLeftChild());
				parent.setRightThread(false);
			}
		} else if (!curr.isRightThread()) {
			// Replace the removed node with its right child
			if(isLeft) {
				parent.setLeftChild(curr.getRightChild());
				parent.setRightThread(false);
			} else {
				parent.setRightChild(curr.getRightChild());
				parent.setRightThread(false);
			}
		} else {
			// Remove leaf node by replacing it with either its left or right link
			if(isLeft) {
				parent.setLeftChild(curr.getLeftChild());
				parent.setLeftThread(true);
			} else {
				parent.setRightChild(curr.getRightChild());
				parent.setRightThread(true);
			}
		}
		
		// Decrement the size of the tree
		size--;
	}
	*/
	
	/**
	 * A threaded node, which includes a boolean for each of its links that
	 * indicates whether or not that link is threaded.
	 */
	private class Node {
		private Node leftChild;
		private Node rightChild;
		private boolean leftThread;
		private boolean rightThread;
		private T data;

		Node(T data) {
			this.leftChild = null;
			this.rightChild = null;
			// Newly inserted nodes will always be leaf nodes, so they will have threaded links
			this.leftThread = true;
			this.rightThread = true;
			this.data = data;
		}

		Node getLeftChild() {
			return leftChild;
		}

		void setLeftChild(Node leftChild) {
			this.leftChild = leftChild;
		}

		Node getRightChild() {
			return rightChild;
		}

		void setRightChild(Node rightChild) {
			this.rightChild = rightChild;
		}

		boolean isLeftThread() {
			return leftThread;
		}

		void setLeftThread(boolean leftThread) {
			this.leftThread = leftThread;
		}

		boolean isRightThread() {
			return rightThread;
		}

		void setRightThread(boolean rightThread) {
			this.rightThread = rightThread;
		}

		T getData() {
			return data;
		}

		@SuppressWarnings("unused")
		void setData(T data) {
			this.data = data;
		}
	} // End of Node class
}
